package LeetCode;

import java.util.LinkedList;
import java.util.List;

public class LC_116_PopulatingNextRightPointersinEachNode {

    public static void main(String[] args) {

    }

    class TreeLinkNode {
        int val;
        TreeLinkNode left, right, next;

        TreeLinkNode(int x) {
            val = x;
        }
    }

    static class Solution {
        public static void connect(TreeLinkNode root) {
            if (root == null) return;
            if (root.left == null && root.right == null) root.next = null;

            List<TreeLinkNode> list = new LinkedList<>();
            list.add(root);
            int count = 0;
            int level = 0;
            int levelCount = 1;
            while (list.size() != 0) {
                TreeLinkNode fis = list.remove(0);
                count++;
                if (list.size() >= 0 && count != levelCount) {
                    fis.next = list.get(0);
                } else {
                    fis.next = null;
                    level++;
                    levelCount = (int) Math.pow(2, level);
                    count = 0;
                }
                if (fis.left != null) list.add(fis.left);
                if (fis.right != null) list.add(fis.right);
            }
        }

    }

}